P3648 [APIO2014]序列分割

dp[t][i]=max{dp[t1][j]+sj(sisj)}dp[t][i]=\max\{dp[t-1][j] + s_j(s_i-s_j)\}

dp[t][i]=max{dp[t1][j]+sjsisj2}dp[t][i]=\max\{dp[t-1][j] + s_js_i-s_j^2\}

假设有两个决策 j<kj<k , 且 jjkk 优。

dp[t1][j]+sjsisj2>dp[t1][k]+sksisk2dp[t-1][j] + s_js_i-s_j^2 > dp[t-1][k] + s_ks_i-s_k^2

(dp[t1][j]sj2)(dp[t1][k]sk2)>si(sksj)(dp[t-1][j]-s_j^2 ) - ( dp[t-1][k] -s_k^2 ) > s_i(s_k-s_j)

#include <cstdio>
#define LL long long
#define Lint long long

const int MAXN = 1e6 , MAXK = 200;
int n , k , s[ MAXN + 5 ] , pre[ MAXK + 5 ][ MAXN + 5 ];
LL dp[ 2 ][ MAXN + 5 ];
int Que[ MAXN + 5 ] , Head , Tail;

LL fx( int i ) { return s[ i ]; }
LL fy( int k , int i ) { return dp[ ( k - 1 ) & 1 ][ i ] - 1ll * s[ i ] * s[ i ]; }
LL deltax( int i , int j ) { return fx( j ) - fx( i ) == 0 ? 1e18 : fx( j ) - fx( i ); }
LL deltay( int k , int i , int j ) { return fy( k , i ) - fy( k , j ); }

int main( ) {
	scanf("%d %d",&n,&k);
	for( int i = 1 ; i <= n ; i ++ )
		scanf("%d",&s[ i ]) , s[ i ] += s[ i - 1 ];
	
	for( int t = 1 ; t <= k ; t ++ ) {
		Head = 1 , Tail = 0; Que[ ++ Tail ] = 0;
		for( int i = 1 ; i <= n ; i ++ ) {
			for( ; Head < Tail && deltay( t , Que[ Head ] , Que[ Head + 1 ] ) <= (__int128)s[ i ] * deltax( Que[ Head ] , Que[ Head + 1 ] ) ; Head ++ );
			dp[ t & 1 ][ i ] = dp[ ( t - 1 ) & 1 ][ Que[ Head ] ] + 1ll * s[ Que[ Head ] ] * ( s[ i ] - s[ Que[ Head ] ] );
			pre[ t ][ i ] = Que[ Head ];
			for( ; Head < Tail && (__int128)deltay( t , Que[ Tail - 1 ] , Que[ Tail ] ) * deltax( Que[ Tail ] , i ) >= (__int128)deltay( t , Que[ Tail ] , i ) * deltax( Que[ Tail - 1 ] , Que[ Tail ] ) ; Tail -- );
			Que[ ++ Tail ] = i;
		}
	}
	
	printf("%lld\n", dp[ k & 1 ][ n ] );
	for( int i = n , t = k ; t >= 1 ; t -- )
		printf("%d ", i = pre[ t ][ i ] );
	return 0;
}